package leetcode100

// TODO 递归+回溯+剪枝 [经典] 【-】 全排列
// TODO https://leetcode.cn/problems/permutations/solution/chou-xiang-cheng-jue-ce-shu-yi-ge-pai-lie-jiu-xian/

func permute(nums []int) [][]int {
	res := [][]int{}
	visited := map[int]bool{} // 为了不重复

	var dfs func(path []int)
	dfs = func(path []int) {
		// 剪枝: 递归结束控制器
		if len(path) == len(nums) {
			temp := make([]int, len(path))
			copy(temp, path)
			res = append(res, temp)
			return
		}
		// 递归
		for _, n := range nums {
			if visited[n] { // 不递归的条件
				continue
			}
			path = append(path, n)
			visited[n] = true
			dfs(path)
			// 回溯
			path = path[:len(path)-1]
			visited[n] = false
		}
	}

	dfs([]int{})
	return res
}
